// https://leetcode.cn/problems/basic-calculator-ii/

// 题干：给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
//      整数除法仅保留整数部分。
//      你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。
//      注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

// 示例：输入：s = "3+2*2"
//      输出：7

// 碎语：遇到表达式求值，利用栈来模拟计算过程
//       注意本题没有括号，也没有负数
//       统一运算，先在首位加上一个+号

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int calculate(string s)
    {
        // 分情况讨论的过程
        // 已经知道乘除的优先级最高，字符不需要用栈

        // 遇到操作符：更新op
        // 遇到数字：
        //      1.先把数字提取出来，tmp
        //      2.分情况讨论，根据op的符号
        //          (1) op=='+',tmp直接入栈
        //          (2) op=='-'-tmp入栈
        //          (3) op=='*'直接乘到栈顶元素上
        //          (4) op=='/'直接除到栈顶元素上

        vector<int> stack;
        int i = 0, n = s.size();
        char op = '+';

        while (i < n){
            if (s[i] == ' ') i++;
            else if (s[i] >= '0' && s[i] <= '9'){
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') tmp = tmp * 10 + (s[i++] - '0'); // 提取数字

                if (op == '+') stack.push_back(tmp);
                else if (op == '-') stack.push_back(-tmp);
                else if (op == '*') stack.back() *= tmp;
                else stack.back() /= tmp;

            }
            else {
                op = s[i];
                i++;
            }
        }

        int ret = 0;
        for (const auto& num : stack) ret += num;

        return ret;
    }
};

int main()
{
    Solution sol;
    string s = "3+2*2";

    cout << sol.calculate(s) << endl;

    return 0;
}